package cn.edu.njust.alg.leetcode;

import java.util.ArrayList;
import java.util.List;

public class Leetcode_93_Restore_IP_Addresses {

	public static void build(String last, int div, String prefix,
			List<String> list) {
		if (last.length() > div * 3 || div > last.length())
			return;
		if (div == 1) {
			int d = Integer.valueOf(last);
			if(last.length()>1 && last.charAt(0)=='0'){
				return;
			}
			if (d < 256 ) {
				list.add(prefix + last);

			}
			return;
		} else {
			if (last.length() > 1) {
				build(last.substring(1), div - 1, prefix + last.substring(0, 1)
						+ ".", list);
			}
			if (last.length() > 2 && last.charAt(0) != '0') {
				build(last.substring(2), div - 1, prefix + last.substring(0, 2)
						+ ".", list);
			}
			if (last.length() > 3 && last.charAt(0) != '0'
					&& Integer.valueOf(last.substring(0, 3)) < 256) {
				build(last.substring(3), div - 1, prefix + last.substring(0, 3)
						+ ".", list);
			}
		}

	}

	public static List<String> restoreIpAddresses(String s) {
		List<String> list = new ArrayList<String>();
		if (s.length() > 12) {
			return list;
		}
		build(s, 4, "", list);
		return list;
	}

	public static void main(String[] args) {
		List<String> list = restoreIpAddresses("24558733");
		for (String s : list) {
			System.out.println(s);
		}
	}

}
